package club.babyf.nativeai.demo.algorithm;

import java.util.Arrays;

/**
 * CoinChange.
 *
 * @author zhanglei.
 * @date 2025/5/8 21:15.
 * @description 最少硬币组合取指定值.
 * 假设我们拥有数量足够多的不同整数面值的硬币，面值之间相互均不可整除，需要利用这些硬币组成指定的金额，要求使用的硬币总数尽可能少。输入参数：coins，为一个整数数组，代表各自的硬币面值；amount，整数，需要组成的金额。输出：所需的硬币数量，若无解则返回-1。
 */
public class _13_CoinChange {

    public static int coinChange(int[] coins, int amount) {
        // 处理金额为0的特殊情况
        if (amount == 0) {
            return 0;
        }

        // 创建动态规划数组，dp[i]表示组成金额i所需的最少硬币数
        int[] dp = new int[amount + 1];
        // 初始化所有金额的硬币数为最大值，表示尚未找到解
        Arrays.fill(dp, Integer.MAX_VALUE);
        // 初始状态：组成金额0不需要任何硬币
        dp[0] = 0;

        // 遍历所有金额，从1到amount，逐步计算最少硬币数
        for (int i = 1; i <= amount; i++) {
            // 遍历所有硬币面值，尝试用每个硬币来减少问题规模
            for (int coin : coins) {
                // 如果当前硬币面值小于等于当前金额i，且金额i-coin有解
                if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) {
                    // 更新dp[i]为当前解和可能的更优解中的较小值
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        // 如果目标金额无解，返回-1；否则返回最少硬币数
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        // 测试示例
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println(coinChange(coins, amount)); // 输出3

        coins = new int[]{3, 5};
        amount = 7;
        System.out.println(coinChange(coins, amount)); // 输出-1
    }

}
